<?php

/**
 * 广度优先遍历
 */
class Node
{
    public $left;
    public $right;
    public $value;
    
    public function __construct($value)
    {
        $this->value = $value;
    }
}

class BFS
{
    /**
     * 非递归
     */
    public function levelOrder($root)
    {
        $res = [];
        $splqueue = new SplQueue();
        $splqueue->enqueue($root);
        while (!$splqueue->isEmpty())
        {
            $root = $splqueue->dequeue();
            $res[] = $root->value;
            if (!is_null($root->left))
            {
                $splqueue->enqueue($root->left);
            }
            
            if (!is_null($root->right))
            {
                $splqueue->enqueue($root->right);
            }
        }
        
        return $res;
    }
}
$a = new Node(10);
$b = new Node(8);
$c = new Node(12);
$d = new Node(7);
$e = new Node(9);
$f = new Node(11);
$g = new Node(13);

$a->left  = $b;
$a->right = $c;
$b->left  = $d;
$b->right = $e;
$c->left  = $f;
$c->right = $g;

$bfs = new BFS();
$res = $bfs->levelOrder($a);
echo 'BFS非递归实现'.implode('-',$res).PHP_EOL;
